/*
 * @lc app=leetcode.cn id=10 lang=cpp
 *
 * [10] 正则表达式匹配
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    bool isMatch(string s, string p) {
        int ss = s.size();
        int pp = p.size();
        // DP[i][j] : first i of s matches first j of p ~
        int DP[ss+1][pp+1];
        memset(DP, 0, (ss+1)*(pp+1)*sizeof(int));
        DP[0][0] = 1;

        auto matches = [&](int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p[j - 1] == '.') {
                return true;
            }
            return s[i - 1] == p[j - 1];
        };

        for (int i=0;i<ss+1;++i){
            for (int j=1;j<pp+1;++j){
                ;
                switch (p[j-1])
                {
                case '*':
                    if (matches(i, j-1)){
                        // ---a
                        // --a*
                        DP[i][j] = DP[i-1][j] or DP[i][j-2];
                    }else{
                        // ---c
                        // --a*
                        DP[i][j] = DP[i][j-2];
                    }
                    break;
                case '.':
                    if (i != 0){
                        // always match once
                        DP[i][j] = DP[i-1][j-1];
                    }else{
                        DP[i][j] = 0;
                    }
                    break;
                default:
                    if (matches(i, j)){
                        // ---a
                        // ---a
                        DP[i][j] = DP[i-1][j-1];
                    }else{
                        DP[i][j] = 0;
                    }
                    break;
                }
            }
        }

        return DP[ss][pp];

        // int stringIndex = 0;
        // int patternIndex = 0;
        // char lastPattern = ' ';

        // while (patternIndex != p.size()){
        //     switch (p[patternIndex])
        //     {
        //     case '.':
        //         if (stringIndex == s.size()){return false;}

        //         stringIndex += 1;
        //         lastPattern = '.';
        //         break;
        //     case '*':
        //         if (stringIndex == s.size()){
        //             patternIndex += 1;
        //             continue;
        //         }

        //         if (lastPattern == '.'){return true;}

        //         while (s[stringIndex] == lastPattern){
        //             stringIndex += 1;
        //         }
        //         break;
        //     default:
        //         if (stringIndex == s.size()){return false;}
                
        //         if (s[stringIndex] != p[patternIndex]){return false;}
                
        //         stringIndex += 1;
        //         lastPattern = p[patternIndex];
        //         break;
        //     }

        //     patternIndex += 1;
        // }

        // return stringIndex == s.size();
    }
};
// @lc code=end

int main(){
    string s = "aab";
    string p = "c*a*b";

    // string s = "aa";
    // string p = "a";
    Solution test;
    printf("%d\n", test.isMatch(s, p));
}
